/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package backtrack;

import java.util.Random;

public class Backtrack {
    
    public int attempts =0;
    public int BOARD_SIZE = 10;
    public int TREE_COUNT = 18;
    private boolean solved = false;
    public int[][] playfield;
    public Tree[] trees;
    public final int GRASS = 0;
    public final int TENT = 1;
    public final int TREE = 2;

    public Backtrack( int boardsize){
	this.BOARD_SIZE = boardsize;
	setupboard();
    }
    private void setupboard(){
	playfield = new int[BOARD_SIZE][BOARD_SIZE];
	trees = new Tree[TREE_COUNT];
	int TreesToPlace = TREE_COUNT;
	Random r = new Random();
	int row,col;
	while(TreesToPlace > 0){
	    row = r.nextInt(BOARD_SIZE);
	    col = r.nextInt(BOARD_SIZE);
	    if(playfield[row][col] == GRASS){
		playfield[row][col] = TREE;
		trees[TREE_COUNT-TreesToPlace] = (new Tree(row,col));
		TreesToPlace--;
		
	    }
	}
    }
    public static void main(String[] args) {
	Backtrack b = new Backtrack(10);
	int attempts = 0;
	
	while(!b.solved){
	   b = new Backtrack(10);
	   b.solve();
	   attempts++;
	}
	/*if(!b.solved){
	    System.out.println("Sorry, couldn't solve it! Tried " + b.attempts +" moves.");
	}*/
	b.print();
	System.out.println("a:"+attempts);
    }
    public void solve(){
	solve(0);
    }
    public void solve(int index){
	
	if(index >= TREE_COUNT){
	    System.out.println("I found a solution.");
	    solved = true;
	    return;
	}
	Tree t = trees[index];
	if(!solved){
	    if(t.row > 0 && canPlaceTent(t.row-1, t.col)){//UP
		attempts++;
		playfield[t.row-1][t.col] = TENT;
		solve(index+1);
		if(!solved){
		    playfield[t.row-1][t.col] = GRASS;
		}
	    }
	}
	if(!solved){
	    if(t.col > 0 && canPlaceTent(t.row, t.col-1)){//LEFT
		attempts++;
		playfield[t.row][t.col-1] = TENT;
		solve(index+1);
		if(!solved){
		    playfield[t.row][t.col-1] = GRASS;
		}
	    }
	}
	if(!solved){
	    if(t.col < BOARD_SIZE-1 && canPlaceTent(t.row, t.col+1)){//RIGHT
		attempts++;
		playfield[t.row][t.col+1] = TENT;
		solve(index+1);
		if(!solved){
		    playfield[t.row][t.col+1] = GRASS;
		}
	    }
	}
	if(!solved){
	    if(t.row < BOARD_SIZE-1 && canPlaceTent(t.row+1, t.col)){//DOWN
		attempts++;
		playfield[t.row+1][t.col] = TENT;
		solve(index+1);
		if(!solved){
		    playfield[t.row+1][t.col] = GRASS;
		}
	    }
	}
	
    }

    public boolean canPlaceTent(int row, int col){
	
	int startRow,startCol,endRow,endCol;
	startRow = Math.max(0, row-1);
	startCol = Math.max(0, col-1);
	endRow = Math.min(BOARD_SIZE-1, row+1);
	endCol = Math.min(BOARD_SIZE-1, col+1);
	if(playfield[row][col] == TREE){
	    return false;
	}
	for(int r=startRow;r<=endRow;r++){
	    for(int c=startCol;c<=endCol;c++){
		if(playfield[r][c] == TENT){
		    return false;
		}
	    }
	    
	}
	return true;
    }
    
    public void print(){
	System.out.println("Printing board!");
	for(int i=0;i<BOARD_SIZE;i++){
	    for(int j=0;j<BOARD_SIZE;j++){
		System.out.print(idToIcon(playfield[i][j]) + " ");
	    }
	    System.out.print(countTentsInRow(i));
	    System.out.println();
	}
	for(int i=0;i<BOARD_SIZE;i++){
	    System.out.print(countTentsInCol(i)+" ");
	}
	System.out.println();
    }
    private int countTentsInRow(int row){
	int ret=0;
	for(int col=0;col<BOARD_SIZE;col++){
	    if(playfield[row][col] == TENT){
		ret++;
	    }
	}
	return ret;
    }
    private int countTentsInCol(int col){
	int ret=0;
	for(int row=0;row<BOARD_SIZE;row++){
	    if(playfield[row][col] == TENT){
		ret++;
	    }
	}
	return ret;
    }
    private String idToIcon(int id){
	switch(id){
	    case GRASS:
		return "-";
	    case TENT:
		return "T";
	    case TREE:
		return "X";
	}
	return "";
    }
    public void printLegend(){
	
	System.out.println("Legend: ");
	System.out.println("Tent:   "+idToIcon(TENT));
	System.out.println("Boom:   "+idToIcon(TREE));
	System.out.println("Grass:  "+idToIcon(GRASS));
	System.out.println();
	
    }
}
